Thuật toán RSA là thuật toán mã hóa công khai được bắt nguồn bởi Ron Rivest, Adi Shamir và Leonard Adleman tại Học viện Công nghệ Massachusetts (MIT) vào năm 1977. Thuật mã hóa này dựa trên một sự thật rằng: để tìm phân tích nhân tử một số N (N=p.q với p,q là hai số nguyên tố) thành tích 2 số nguyên tố thì khó khăn hơn rất nhiều lần tính ra tích N của hai số nguyên tố p,q. Với tính toán cổ điển, hàm N(p,q) = pq là một hàm một chiều tức là việc tính ra N từ p và q có độ phức tạp nhỏ, O(0), còn việc tính ra p và q từ N có độ phức tạp cao. Ngay cả những siêu máy tính hiện đại mạnh mẽ nhất cũng sẽ cần nhiều thời gian hơn cả tuổi của vũ trụ nếu phân tích nhân tử một số 400 chữ số[cần dẫn nguồn]. Tính chất này được áp dụng cho việc xây dựng và ứng dụng mã hóa RSA.

Nếu có phương án phân tích nhân tử một số nguyên N nhanh thành p và q thì mã hóa RSA sẽ không còn an toàn trước các cuộc tấn công bẻ khóa. Thuật toán Shor đã thực hiện được việc phân tích nhân tử một số nguyên N thành p và q nhanh hơn các thuật toán cổ điển: chỉ trong thời gian đa thức. Ta có thể cần tới O((log N)2(log log N)(log log log N)) cổng lượng tử sử dụng phép nhân nhanh chóng khi tính toán và việc này hoàn toàn có thể giải quyết hiệu quả bằng máy tính lượng tử. Như vậy, nếu có một máy tính lượng tử có đủ số lượng qubit có thể hoạt động mà không bị ảnh hưởng bởi nhiễu lượng tử và các hiện tượng phục hồi tách sóng lượng tử khác, thuật toán Shor có thể được sử dụng để phá khóa RSA. Đây là một động lực mạnh mẽ cho việc thiết kế và xây dựng các máy tính lượng tử và cho việc nghiên cứu các thuật toán máy tính lượng tử học. Nó cũng đã tạo điều kiện nghiên cứu về hệ thống mã hóa mới an toàn trước các máy tính lượng tử, được gọi chung là mật mã hậu lượng tử.